package leetcode_700;

import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

/**
 *@author 周杨
 *StickersToSpellWord_691_  用字典里的单词重构字符串 问最小次数
 *describe:应该用动态规划 但是没有看懂 AC 45% 
 *see:https://blog.csdn.net/thesnowboy_2/article/details/78180542
 *2018年10月9日 上午11:00:17
 */
public class StickersToSpellWord_691_ {
	    public int minStickers1(String[] stickers, String target) {
	        int n = target.length(), m = 1 << n; // if target has n chars, there will be m=2^n-1 subset of characters in target
	        int[] dp = new int[m];
	        for (int i = 0; i < m; i++) dp[i] = Integer.MAX_VALUE; // use index 0 - 2^n-1 as bitmaps to represent each subset of all chars in target
	        dp[0] = 0; // first thing we know is : dp[empty set] requires 0 stickers,
	        for (int i = 0; i < m; i++) { // for every subset i, start from 000...000。（起点这里很重要，因为大的集合往往依赖于小的集合）
	            if (dp[i] == Integer.MAX_VALUE) continue;
	            for (String s : stickers) { // try use each sticker as an char provider to populate 1 of its superset, to do that:
	                int sup = i;//关键代码（下面：在i上面加入一个单词后的效果）
	                for (char c : s.toCharArray()) { // for each char in the sticker, try apply it on a missing char in the subset of target
	                    for (int r = 0; r < n; r++) {
	                        if (target.charAt(r) == c && ((sup >> r) & 1) == 0) {  //如果target中包含字符c , 并且sup中相应位置没有c。
	                            sup |= 1 << r;//在sup中相应位置，加入c，形成新的集合。
	                            break;
	                        }
	                    }
	                }
	               // after you apply all possible chars in a sticker, you get an superset that take 1 extra sticker than subset
	               // would take, so you can try to update the superset's minsticker number with dp[sub]+1;
	                dp[sup] = Math.min(dp[sup], dp[i] + 1);//判断是否需要替换原来sup中的值。
	            }
	        }
	        return dp[m - 1] != Integer.MAX_VALUE ? dp[m - 1] : -1;
	    }
	

	
	
	public static void main(String[] args) {
		StickersToSpellWord_691_ test=new StickersToSpellWord_691_();
		System.out.println(test.minStickers(new String[] {"notice","possible"
				}, "basicbasic"));
	}
	
	/**
	 * describe:这种贪心算法遇到now值相等就无法做出最优权衡的解 如["these","guess","about","garden","him"] "atomher"
	 * 2018年10月9日 上午10:25:18
	 */
	public int minStickers(String[] stickers, String target) {
        Map<Character,Integer> targetMap=new HashMap<Character,Integer>();
        char[] chars=target.toCharArray();
        for(int i=0;i<target.length();++i) {
        	Integer num=targetMap.get(chars[i]);
        	if(num==null) {
        		num=1;
        	}
        	else {
        		num++;
        	}
        	targetMap.put(chars[i], num);
        }
        Map<Integer,Map<Character,Integer>> stickerMap=
        		new HashMap<Integer,Map<Character,Integer>>();
        //构造字典map
        for(int i=0;i<stickers.length;++i) {
        	Map<Character,Integer> nowMap=
        			new HashMap<Character,Integer>();
        	char[] chs=stickers[i].toCharArray();
        	for(int j=0;j<chs.length;++j) {
        		Integer now=nowMap.get(chs[j]);
        		if(now==null) {
        			now=1;
        		}
        		else {
        			now++;
        		}
        		nowMap.put(chs[j], now);
        	}
        	stickerMap.put(i, nowMap);
        }
        int res=0;
        int size=chars.length;//这么多字母被减完就ok
        while(size>0) {//开始用贪心算法 每次减去能减的最大的字典
        	int max=0;
        	int index=-1;
        	Set<Entry<Character, Integer>> set=targetMap.entrySet();
        	for(int i=0;i<stickerMap.size();++i) {
        		int now=0;
        		Map<Character,Integer> nowMap=stickerMap.get(i);
        		for(Entry<Character, Integer> entry:set) {
        			Character key=entry.getKey();
        			Integer value=entry.getValue();
        			Integer rest=nowMap.get(key);
        			if(rest!=null) {
        				now+=rest>value?value:rest;//要么减完
        			}
        		}
        		if(now>max) {
            		max=now;
            		index=i;
            	}
        	}
        	if(max==0)
        		return -1;
        	size-=max;
        	Map<Character,Integer> stick=stickerMap.get(index);
        	for(Entry<Character, Integer> entry:set) {
        		Character key=entry.getKey();
    			Integer value=entry.getValue();
    			Integer rest=stick.get(key);
    			if(rest!=null) {
    				if(rest>value) {
    					targetMap.put(key, 0);
    				}
    				else {
    					targetMap.put(key,value-rest);
    				}
    			}
        	}
        	++res;
        }
        return res;
    }
}
